﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Team6_Algorithms.Sorting
{
    /// <summary>
    /// Made by Pascal Schotman
    /// Static class used to hold the static Bogosort function
    /// </summary>
    public static class BogoSort
    {
        private static Random rnd;

        /// <summary>
        /// Run the BogoSort
        /// </summary>
        /// <param name="items">A byte[] containing trhe items to be sorted.</param>
        /// <returns>A sorted list of the items.... Eventually</returns>
        public static byte[] Sort(byte[] items)
        {
            while (!inOrder(items))
                shuffle(items);
            return items;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="items"></param>
        private static void shuffle(byte[] items)
        {
            if (rnd == null) rnd = new Random();
            for (int i = 0; i < items.Length; i++)
                Swap(items, i, rnd.Next(0, items.Length - 1));
        }

        private static void Swap(byte[] items, int item1, int item2)
        {
            byte temp = items[item1];
            items[item1] = items[item2];
            items[item2] = temp;
        }


        private static bool inOrder(byte[] items)
        {
            for (int i = 0; i < items.Length - 1; i++)
            {
                if (items[i] > items[i + 1])
                    return false;
            }
            return true;
        }

        /// <summary>
        /// Sorts the List using BogoSort. Sorts directly on the list given in the parameters.
        /// </summary>
        /// <typeparam name="T">Type of list</typeparam>
        /// <param name="list">The List of items to be sorted</param>
        public static void Sort<T>(List<T> list) where T : IComparable
        {
            while (!list.isSorted())
            {
                list.Shuffle();
            }
        }

        private static bool isSorted<T>(this IList<T> list) where T : IComparable
        {
            if (list.Count <= 1)
                return true;
            for (int i = 1; i < list.Count; i++)
                if (list[i].CompareTo(list[i - 1]) < 0) return false;
            return true;
        }

        private static void Shuffle<T>(this IList<T> list)
        {
            Random rand = new Random();
            for (int i = 0; i < list.Count; i++)
            {
                int swapIndex = rand.Next(list.Count);
                T temp = list[swapIndex];
                list[swapIndex] = list[i];
                list[i] = temp;
            }
        }
    }
}
